package com.faiz.algorithm;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class MedianFinder {


    public Random random;
    public List<Integer> list;

    /**
     * initialize your data structure here.
     */
    public MedianFinder() {
        random = new Random(5);
        list = new ArrayList<>();
    }

    public void addNum(int num) {
        list.add(Integer.valueOf(num));
    }

    public double findMedian() {
        int[] nums = list.stream().mapToInt(Integer::intValue).toArray();
        int length = nums.length;
        int start = 0;
        int end = length - 1;
        int index = partition(nums, start, end);
        int middle = (length - 1) / 2;
        while (index != middle) {
            if (index > middle) {
                end = index - 1;
                index = partition(nums, start, end);
            } else {
                start = index + 1;
                index = partition(nums, start, end);
            }
        }
        if (length % 2 != 0) {
            return (double) nums[middle];
        } else {
            int result = nums[middle];
            start = 0;
            end = length - 1;
            while (index != middle + 1) {
                if (index > middle + 1) {
                    end = index - 1;
                    index = partition(nums, start, end);
                } else {
                    start = index + 1;
                    index = partition(nums, start, end);
                }
            }
            return ((double) result + (double) nums[middle + 1]) / 2;
        }
    }


    public int generateRandom(int min, int max) {
        return random.nextInt(max - min + 1) + min;
    }

    public int partition(int[] nums, int start, int end) {
        int index = generateRandom(start, end);
        swap(nums, start, index);
        int i = start;
        int j = end;
        boolean reverseFlag = true;//控制方向
        while (i != j) {
            if (reverseFlag) {
                if (nums[j] < nums[i]) {
                    swap(nums, i, j);
                    reverseFlag = false;
                } else {
                    j--;
                }
            } else {
                if (nums[i] > nums[j]) {
                    swap(nums, i, j);
                    reverseFlag = true;
                } else {
                    i++;
                }
            }
        }
        return i;
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}
